public class RegBST<K extends Comparable<K>, V> {
	protected BSTNode<K, V> root;

	/***
	 * Constructs an empty BST
	 */
	public RegBST() {
		root = null;
	}

	/***
	 * Constructs a BST with one node
	 * 
	 * @param key
	 *            root key
	 * @param value
	 *            root value
	 */
	public RegBST(K key, V value) {
		root = new BSTNode<K, V>(key, value);
	}

	/**
	 * Set root. For testing purposes only
	 * 
	 * @param root
	 *            new root
	 */
	public void setRoot(BSTNode<K, V> root) {
		this.root = root;
	}

	/**
	 * Returns the root. For testing purposes only
	 * 
	 * @return the root
	 */
	public BSTNode<K, V> getRoot() {
		return root;
	}

	/**
	 * Preorder traversal of the tree
	 * 
	 * @return node toSTrings concatenated in preorder traversal
	 */
	public String preorder() {
		return preorder(root, null);
	}

	/**
	 * Helper function for traversal
	 * 
	 * @param t
	 *            recursive paramter
	 * @param s
	 *            unused
	 * @return preorder traversal of subtree
	 */
	private String preorder(BSTNode<K, V> t, String s) {
		if (t == null) {
			return "";
		}

		return t.toString() + preorder(t.getLeft(), s)
				+ preorder(t.getRight(), s);
	}

	/**
	 * Perform a postorder traversal
	 * 
	 * @return node strings concatenated in search order
	 */
	public String postorder() {
		return postorder(root, null);
	}

	/**
	 * Traversal helper function
	 * 
	 * @param t
	 *            recursive parameter
	 * @param s
	 *            unused
	 * @return traversal of subtree
	 */
	private String postorder(BSTNode<K, V> t, String s) {
		if (t == null) {
			return "";
		}

		return postorder(t.getLeft(), s) + postorder(t.getRight(), s)
				+ t.toString();
	}

	/**
	 * Perform an inorder traversal
	 * 
	 * @return node strings concatenated in search order
	 */
	public String inorder() {
		return inorder(root, null);
	}

	/**
	 * Traversal helper function
	 * 
	 * @param t
	 *            recursive paramter
	 * @param s
	 *            unused
	 * @return traversal of subtree
	 */
	private String inorder(BSTNode<K, V> t, String s) {
		if (t == null) {
			return "";
		}

		return inorder(t.getLeft(), s) + t.toString()
				+ inorder(t.getRight(), s);
	}

	/**
	 * Level order traversal 
	 * 
	 * @return String of nodes in level order
	 */
	public String levelorder() {
		return levelorder(root);
	}

	/**
	 * Level order traversal helper function
	 * @param t node that begins the level order traversal
	 * @return String of nodes in level order
	 */
	public String levelorder(BSTNode<K, V> t) {
		if (t == null)
			return "";

		String ret = "";
		java.util.LinkedList<BSTNode<K, V>> v = new java.util.LinkedList<BSTNode<K, V>>();
		
		v.add(t);

		while (!v.isEmpty()) {
			t = v.remove(0);
			ret += t.toString();

			if (t.getLeft() != null)
				v.add(t.getLeft());
			if (t.getRight() != null)
				v.add(t.getRight());
		}
		return ret;
	}

	/**
	 * Insert element into the tree
	 * 
	 * @param key
	 *            key of new element
	 * @param value
	 *            value of new element
	 */
	public void insert(K key, V value) {
		root = insert(root, key, value);
	}

	/**
	 * Helper function for insertion
	 * 
	 * @param t
	 *            recursive parameter
	 * @param key
	 *            key of new element
	 * @param value
	 *            value of new element
	 * @return new root of the subtree
	 */
	private BSTNode<K, V> insert(BSTNode<K, V> t, K key, V value) {
		if (t == null) 
		{
			t = new BSTNode<K, V>(key, value);
		} 
		else if (t.getKey().compareTo(key) > 0) 
		{
			t.setLeft(insert(t.getLeft(), key, value));
		} 
		else if (t.getKey().compareTo(key) < 0) 
		{
			t.setRight(insert(t.getRight(), key, value));
		}

		return t;
	}

	/**
	 * Remove an element from the tree
	 * 
	 * @param key
	 *            key of element to remove
	 */
	public void remove(K key) {
		root = remove(root, key);
	}

	/**
	 * Helper function for removal.
	 * 
	 * @param t
	 *            recursive parameter
	 * @param key
	 *            key of element to remove
	 * @return new root of subtree
	 */
	private BSTNode<K, V> remove(BSTNode<K, V> t, K key) {
		if (t != null) 
		{
			if (t.getKey().compareTo(key) > 0) 
			{
				t.setLeft(remove(t.getLeft(), key));
			} 
			else if (t.getKey().compareTo(key) < 0) 
			{
				t.setRight(remove(t.getRight(), key));
			} 
			else 
			{
				if (t.getLeft() == null) 
				{
					t = t.getRight();
				} 
				else if (t.getRight() == null) 
				{
					t = t.getLeft();
				} 
				else 
				{
					// Two children - here's where it get's interesting
					BSTNode<K, V> suc = getSucc(t);
					t.setKey(suc.getKey());
					t.setValue(suc.getValue());
					t.setRight(remove(t.getRight(), t.getKey()));
				}
			}
		}
		return t;
	}

	/**
	 * Gets the successor of a given node
	 * 
	 * @param t
	 *            node to find successor of
	 * @return successor of t
	 */
	public BSTNode<K, V> getSucc(BSTNode<K, V> t) {
		
		return getSuccHelper(t.getRight());
	}
	
	private BSTNode<K, V> getSuccHelper(BSTNode<K, V> t) {
		if(t.getLeft() == null)
			return t;
		else
			return getSuccHelper(t.getLeft());
	}

	/**
	 * Retrieves data associated with a key
	 * 
	 * @param key
	 *            key to search for
	 * @return value
	 */
	public V find(K key) {
		return find(root, key);
	}

	/**
	 * Helper function for value retrieval
	 * 
	 * @param t
	 *            recursive parameter
	 * @param key
	 *            key to search for
	 * @return value
	 */
	private V find(BSTNode<K, V> t, K key) {
		if (t == null) {
			return null;
		} else if (t.getKey().compareTo(key) > 0) {
			return find(t.getLeft(), key);
		} else if (t.getKey().compareTo(key) < 0) {
			return find(t.getRight(), key);
		}

		return t.getValue();
	}
}